/**
 * @param {number[][]} buildings
 * @return {number[][]}
 */
export var getSkyline = function (buildings) {
  // 查出所有座标点，前按从左到右排序
  const points = []
  for (const [l, r, h] of buildings) {
    // 左端点高度用负数表示
    points.push([l, -h], [r, h])
  }
  // 按左到右排序，如果两个座标相同，则左端点排在右端点前面（左端点高度设为负数，所以同高左必排在前）
  points.sort((a, b) => a[0] - b[0] || a[1] - b[1])
  const ans = []
  const heights = [0]
  let preHeight = null // 记录上一个的最大高度，高度有变化就要加点到ans
  for (let point of points) {
    const [x, h] = point
    if (h < 0)
      heights.splice(findIdx(heights, -h, 1), 0, -h) // h < 0说明此为左端点 ，推入左端点的高度
    else heights.splice(findIdx(heights, h, 0), 1) // h > 0说明此为右端点，删除右端点的高度
    const maxHeight = heights[heights.length - 1]
    if (preHeight !== maxHeight) {
      ans.push([x, maxHeight])
      preHeight = maxHeight
    }
  }
  return ans
}

function findIdx(arr, target, flag = 0) {
  let left = 0
  let right = arr.length - 1
  let ans = -1
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    if (arr[mid] === target) return mid
    if (arr[mid] < target) {
      if (flag < 0) ans = mid
      left = mid + 1
    } else {
      if (flag > 0) ans = mid
      right = mid - 1
    }
  }
  return flag > 0 && ans == -1 ? arr.length : ans
}
